# Q: 集合中找出最大货最小的N个元素
import heapq  # 可以通过调用heapq模块来建立堆这种数据结构，同时heapq模块也提供了相应的方法来对堆做操作
nums = [1,3,7,3,87,-12,12,14,9,23]
print (heapq.nlargest(3,nums))  # 取最大的3个元素
print(heapq.nsmallest(3,nums))  # 取最小的3个元素
# 还能接受一个参数key
p = [{'name': 'IBM', 'shares': 100, 'price': 91.1},
     {'name': 'AAPL', 'shares': 50, 'price': 543.22},
     {'name': 'FB', 'shares': 35, 'price': 21.33},
     {'name': 'YHOO', 'shares': 45, 'price': 74.3},
     {'name': 'ACME', 'shares': 75, 'price': 115.9}]
print(heapq.nsmallest(3,p,key=lambda s: s['price']))
# 更好的性能找最大最小元素
heapq.heapify(nums)  # 以线性时间将一个列表转化为堆
print(nums)


# Q: 实现一个队列, 能够以给定的优先级来对元素排序, 且每次pop操作时都会返回优先级最高的那个元素
class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item)) # 往堆中插入一条新的值
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1] # 往堆中弹出一个记录

class Item:
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return 'Item ({!r})'.format(self.name)

if __name__ == '__main__':
    q = PriorityQueue()
    q.push(Item('foo'),2)
    q.push(Item('bar'), 5)
    q.push(Item('spam'), 4)
    q.push(Item('grok'), 2)
    q.push(Item('foo'), 1)
    print(q.pop())
    print(q.pop())
    print(q.pop())